1. Field of the Invention
The present invention relates to a relational database system and, more particularly, to query optimization techniques for a relational database system having foreign functions.
2. Description of the Related Art
Relational database systems provide the ability to conveniently query the data stored in their database. However, in many applications, there is a need to integrate data and operations that are external to the database (referred to as foreign functions). For example, it would be convenient to invoke mathematical functions and UNIX library functions as part of a relational query. Moreover, for many problem domains, highly tuned applications exist. The ability to exploit such existing applications is important since redevelopment can be prohibitively expensive. Also, for many applications, only part of the data that is needed may be stored in the database. Additional data may reside externally. Access to external data is provided by a set of interface routines.
As an example, many specialized Geographic Information Systems (GIS) are available today that provide the ability to store and access geographic data. On the other hand, information on attributes (e.g., population of a city) is usually stored in a relational database. Therefore, for GIS applications, the ability to use a relational query language as well as the ability to invoke functions provided by the GIS package is important. In general, the ability to invoke foreign functions in a relational query is important to develop applications.
To illustrate the key challenges to optimization introduced by foreign functions, consider two examples taken from an earlier application described in Kolovson et al., Interoperability of spatial and attribute data managers: A case study, Proceedings of the 3rd International Symposium on Large Spatial Databases, Miami, Fla., 1992. This known application was built in the Papyrus project, see Connors et al., The papyrus integrated data server, Proceedings of the First International Conference on Parallel and Distributed Systems, Miami, Fla., 1991. The application allows one to access information about businesses and their locations in the Bay Area of northern California. The application is built on top of the ETAK MapEngine and a relational storage manager. ETAK Inc. of Menlo Park, Calif. is a company that designs vehicle navigation equipment and produces digital map databases.
The MapEngine is a geographic data manager that provides the ability to store and query maps. The MapEngine stores the locations of the business establishments in the Bay Area in a file Map. The relational database is used to store attribute information about businesses (e.g., type of business) in a table Business. Each tuple of this table also stores an additional attribute which acts as a key for the MapEngine. The latter uses this key to look up the location of the business. Similarly, each record in MapEngine points to the tuple in the table Business of the relational database where the attribute information about the corresponding business establishment is maintained. Thus, queries are permitted to span the relational system as well as the MapEngine.